package longest_string_of_subroutines;

class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().longestPalindrome("aacabdkacaa"));
    }
}

public class Solution {
    public String longestPalindrome(String s) {
        //字符串长度
        int len = s.length();
        //特殊情况
        if (len < 2) return s;
        //创建状态转义数组
        boolean d[][] = new boolean[len][len];
        //定义最长的回文串长度
        int maxLen = 1;
        //定义最长回文串的起始位置
        int start = 0;
        //得到字符数组
        char[] array = s.toCharArray();
        //当回文串长度大于1的时候
        for (int L = 1; L <= len; L++) {
            //依次枚举各个长度为L的串，后面的L计算将用到前面的计算结果
            for (int i = 0; i < len; i++) {
                //确定右边界
                int j = i + L - 1;
                //如果右边界越界
                if (j > len - 1) break;
                //如果不存在越界就要判定这两个字符是否是左右相等的
                if (array[i] == array[j]) {
                    if (i < j) {
                        if (i == j - 1){
                            d[i][j] = true;
                            start = i;
                            maxLen = 2;
                        }
                        else if (d[i + 1][j - 1]) {
                            d[i][j] = true;
                            start = i;
                            maxLen = L;
                        }
                    }
                    else d[i][j] = true;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}
